---
id: 5900f4b41000cf542c50ffc7
title: 'Завдання 328: найменш затратний пошук'
challengeType: 1
forumTopicId: 301985
dashedName: problem-328-lowest-cost-search
---

# --description--

Ми намагаємось знайти невідоме число з множини цілих чисел {1, 2, ..., $n$} за допомогою запитань. Кожне число (запитання) має <u>плату, яка дорівнює названому числу</u> і ми отримуємо одну з трьох можливих відповідей:

- «Назване число менше за невідоме число», або
- «Так, це воно!», або
- «Назване число більше за невідоме число».

Враховуючи значення $n$, оптимальна стратегія мінімізує загальну плату (тобто суму всіх названих чисел) <u>в найгіршому можливому випадку</u>. Наприклад:

Якщо $n = 3$, то першим названим числом може бути <strong>2</strong>. Відповідь одразу приведе до знаходження невідомого числа (загальна плата = 2).

Якщо $n = 8$, ми можемо використати стратегію «бінарного пошуку»: першим названим числом буде <strong>4</strong>, а якщо невідоме число більше ніж 4, нам знадобиться одне або два додаткових запитання. Нехай другим названим числом буде <strong>6</strong>. Якщо невідоме число більше ніж 6, нам доведеться поставити третє запитання, щоб вирішити між 7 та 8. Тому третім названим числом буде <strong>7</strong>, а загальною платою в найгіршому можливому випадку буде $4 + 6 + 7 = \mathbf{\color{red}{17}}$.

Плату в найгіршому можливому випадку за умови $n = 8$ можна значно зменшити, використавши <strong>5</strong> як перше назване число. Якщо нам кажуть, що невідоме число більше ніж 5, то наступним названим числом буде <strong>7</strong>, і ми знатимемо приховане число (загальна плата $5 + 7 = \mathbf{\color{blue}{12}}$). Якщо нам кажуть, що невідоме число менше ніж 5, то другим названим числом буде <strong>3</strong>, а якщо невідоме число менше ніж 3, то третім названим числом буде <strong>1</strong> (загальна плата $5 + 3 + 1 = \mathbf{\color{blue}{9}}$). Оскільки $\mathbf{\color{blue}{12 > 9}}$, то платою в найгіршому випадку цієї стратегії буде <strong><span style="color: red;">12</span></strong>. Цей результат кращий, ніж у стратегії «бінарного пошуку», а також кращий або рівний будь-яким іншим стратегіям. Таким чином ми щойно описали оптимальну стратегію за умови $n = 8$.

Нехай $C(n)$ буде платою в найгіршому випадку оптимальної стратегії для $n$, як описано вище. Отже, $C(1) = 0$, $C(2) = 1$, $C(3) = 2$ та $C(8) = 12$.

Аналогічно, $C(100) = 400$ та $\displaystyle\sum_{n = 1}^{100} C(n) = 17575$.

Знайдіть $\displaystyle\sum_{n = 1}^{200\\,000} C(n)$.

# --hints--

`lowestCostSearch()` має повернути `260511850222`.

```js
assert.strictEqual(lowestCostSearch(), 260511850222);
```

# --seed--

## --seed-contents--

```js
function lowestCostSearch() {

  return true;
}

lowestCostSearch();
```

# --solutions--

```js
// solution required
```
